import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import static java.lang.Integer.parseInt;

/**
 * Problem which is solved in this class:
 *
 * Tomya is a girl. She loves Chef Ciel very much.
 Tomya like a positive integer p, and now she wants to get a receipt of Ciel's restaurant whose total price is exactly p. The current menus of Ciel's restaurant are shown the following table.

 Name of Menu	                                price
  eel flavored water                        	1
 deep-fried eel bones                       	2
 clear soup made with eel livers                4
 grilled eel livers served with grated radish	8
 savory egg custard with eel                	16
 eel fried rice (S)                             32
 eel fried rice (L)                         	64
 grilled eel wrapped in cooked egg          	128
 eel curry rice                             	256
 grilled eel over rice                      	512
 deluxe grilled eel over rice               	1024
 eel full-course                                2048

 Note that the i-th menu has the price 2i-1 (1 ≤ i ≤ 12).
 Since Tomya is a pretty girl, she cannot eat a lot. So please find the minimum number of menus whose total price is exactly p. Note that if she orders the same menu twice, then it is considered as two menus are ordered. (See Explanations for details)

 Input:

 The first line contains an integer T, the number of test cases. Then T test cases follow. Each test case contains an integer p.

 Output:

 For each test case, print the minimum number of menus whose total price is exactly p.

 Constraints:

 1 ≤ T ≤ 5
 1 ≤ p ≤ 100000 (105)
 There exists combinations of menus whose total price is exactly p.
 */



public class CielReceipt {


    private static int[] total;
    private static final int MAX_PRICE = 2048;
    private static int countOfDishes;

    public static void main(String args[]) {

        total = getInputData();

        for (int aTotal : total) {
            System.out.println(getMinimumDishes(aTotal, MAX_PRICE));
        }

    }

    static int getMinimumDishes(int total, int price) {

        if ((total % price == 0) && (price >= 1) && (total > 0)) {
            countOfDishes = total / price;
            return countOfDishes;
        } else if ((total < price) && (total > 0)) {
            getMinimumDishes(total, price / 2);
        } else if (total > price) {
            countOfDishes = total / price;
            total = total % price;
            countOfDishes += getMinimumDishes(total, price / 2);
        } else if (total == 0) {
            return 0;
        }
        return countOfDishes;
    }


    static int[] getInputData() {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        try {
            int count = parseInt(in.readLine());
            total = new int[count];
            for (int i = 0; i < count; i++) {
                total[i] = parseInt(in.readLine());

            }
        } catch (IOException e) {
            System.out.println(e.getMessage());

        }
        return total;
    }
}

